package main

/**
归并排序
1️⃣ 分解（Divide）
把数组一分为二，递归地对左右两部分继续分解，直到每个子数组只包含一个元素（此时认为已排好序）。
2️⃣ 解决（Conquer）
两两合并已排序好的子数组，合并成更大的有序数组。
3️⃣ 合并（Combine）
不断向上合并，最终变成一个完整有序数组。

二叉树回溯 左右中 中序遍历
*/

func mergeSort(nums []int) []int {
	// 跳出条件
	if len(nums) <= 1 {
		return nums
	}

	// 先拆
	mid := len(nums) / 2
	left := mergeSort(nums[:mid])
	right := mergeSort(nums[mid:])

	// left,right有序，合并两者
	return merge(left, right)
}

// 合并left和right left、right都是有序的
func merge(left []int, right []int) []int {
	i, j := 0, 0
	var output []int

	for i < len(left) && j < len(right) {
		if left[i] < right[j] {
			output = append(output, left[i])
			i++
		} else {
			output = append(output, right[j])
			j++
		}
	}

	output = append(output, left[i:]...) // 上轮最后left[i]和right[j]其实并没有加入output中
	output = append(output, right[j:]...)

	return output
}
